public class FindElement {

	/*
	 * Given a sorted array of n integers that has been rotated an unknown
	 * number of times, give an O(log n) algorithm that finds an element in the
	 * array. You may assume that the array was originally sorted in increasing
	 * order. EXAMPLE: Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)
	 * Output: 8 (the index of 5 in the array)
	 */

	public static void main(String[] args) {

		int[] array = { 22, 24, 25, 40, 44, 50, 1, 4, 9, 12, 15, 18, 19, 20, 21 };

		System.out.println(getIndex(array, 21, 0, array.length - 1));

	}

	private static int getIndex(int[] array, int v, int i, int j) {

		int middle = (i + j) >> 1;
		int value = array[middle];

		if (value == v) {

			return middle;

		} else if (i >= j) {

			return -1;
		}

		if (array[0] < value) {

			if (v > value) {
				return getIndex(array, v, middle + 1, j);
			} else {
				if (array[i] <= v) {
					return getIndex(array, v, i, middle - 1);
				} else {
					return getIndex(array, v, middle + 1, j);
				}
			}

		} else {

			if (v < value) {
				return getIndex(array, v, i, middle - 1);
			} else {
				if (array[j] >= v) {
					return getIndex(array, v, middle + 1, j);
				} else {
					return getIndex(array, v, i, middle - 1);
				}
			}
		}
	}
}
